Ordering Requests: Part I
Learn how to ensure that replicas process requests in the same order.
Requirements for order#
Replica coordination requires (alongside the agreement property) the order property, which states that every non-faulty state machine replica processes requests in the same relative order. One way to implement order is to assign unique identifiers to each request. This way, we can manage the order in which replicas process requests in the unique identifiers' total order.
With replicas processing requests according to the order of their unique identifiers, we define a request as stable at a state machine replica
Order implementation requires a method to assign unique identifiers to requests. This method also needs to be constrained by the assumptions that a client can make about the order in which state machines process requests:
[
] A state machine processes requests by one of its clients in the order the client issued the requests. For example, a client issues requests to a state machine in the following order: request , then request , and then request . In this case, will process first, then , and then . [
] If a client makes a request to state machine that causes another client to make a request to , then will process before .
These two assumptions do not necessarily mean that
Let's discuss three ways in which we can implement order implementation. Replicas will need a test to classify a request as stable. We will have a stability test section for all our order implementations where we explain how replicas can check whether a request is stable.
Note: You can review how unique identifiers can be generated in the Sequencer chapter.
Order implementation#
Method 1: Logical clocks#
A logical clock is a function that maps events to integers. A logical clock
Implementation#
We can implement logical clocks in a distributed system by associating a counter
Process
increases after each event at . When
receives a message with a timestamp , resets based on the following equation:
The figure above shows how our implementation works with three processes
For an event
Stability test#
Now that we understand the use of logical clocks for order implementation, let's devise a stability test to allow replicas to test whether a request is stable.
Note: The method of using logical clocks for order implementation will not work in an asynchronous environment (where network messages can take arbitrarily long to be delivered and nodes can take arbitrarily long to process, and hence it is impossible to detect if a node has failed). Additionally, the methods of this subsection also don't apply to Byzantine failures. This section only applies to fail-stop failures where messages take a bounded time to deliver on the network.
We will require a mechanism to determine if a node or message has been delayed for a particular duration to classify it as faulty. We will discuss failure detection for fail-stop failures and make the following assumptions:
FIFO channels assumption: Messages between nodes are delivered in the order the sender sent them. This is equivalent to saying that nodes have FIFO channels between them.
Failure detection assumption: A node
can only detect that another node has failed after receiving the last message sent by to .
The second assumption is consistent with the first since fail-stop failure will occur at a node after it has sent its last message, which its recipient will receive after all other messages.
Based on the above assumptions, we can use the following stability test:
Every client makes a null request to the state machine after a set time.
A request will be stable at replica
if it has received a request with a larger timestamp from every non-faulty client.
1 of 8
2 of 8
3 of 8
4 of 8
5 of 8
6 of 8
7 of 8
8 of 8
Any client
Method 2: Synchronized real-time clocks#
Another way to generate unique identifiers is by using approximately synchronized real-time clocks. If
We'll implement the following restrictions to enforce the assumptions (
For
, we assume a client cannot make two or more requests between successive clock ticks. For a resolution of seconds for processor clocks, every client can make at most one request every seconds. For two requests made by a client between successive clock ticks, a state machine could not tell which request was made first by . For
, we assume clocks are synchronized to a better degree than the minimum message delivery time. If the difference in time on clocks on different nodes is within seconds, then it must take more than seconds for a message from a client to reach another. If we do not have this restriction, a client can request with a smaller unique identifier than a request that caused to make .
Stability test#
We will formulate a stability test using the bounds on message delivery time. We will assume that
Once the clock on a node, say node
A request
The problem with this stability test is that it forces a state machine to lag behind its clients by
A request
The second test is not passed if a node refuses to make requests. We can combine the two tests, and a request is considered stable if it passes either test. In that case, the lag
Note: Placing an upper bound on the network messages is not an easy task. Google Spanner's TrueTime API achieved that feat by ensuring that clock times remain within a known bound.
Point to ponder
Question
In practical terms, what is one of the challenges of implementing synchronized real-time clocks?
Synchronizing real-time clocks with reasonably short bounds is challenging. Although Spanner’s TrueTime has achieved it, it requires maintaining multiple atomic and GPS clocks. Such machinery might not be available to everyone (though it might change in the future due to the services like clocksync that provide TrueTime-like facilities as a service).
Additionally, there can be a few instances when the time-bound can increase momentarily, even for a TrueTime setup. During those scenarios, different components of the systems artificially slow down to provide consistency guarantees. With a potentially variable , the stability test can fail.
What’s next?#
So far, we have discussed protocols for generating unique identifiers for requests where the client proposes the unique identifier. In the next lesson, we will discuss a protocol where state machine replicas propose and agree on a unique identifier for a request.
Replication and Coordination of State Machines
Ordering Requests: Part II